/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 言初
 * Date: 2023-03-24
 * Time: 19:45
 */
import java.util.*;
public class Test{






    public static void main29(String[] args) {
        //（反转部分数组）
        Scanner in = new Scanner(System.in);
        int n=in.nextInt();
        int[] array=new int[n];
        for(int i=0;i<n;i++){
            array[i]=in.nextInt();
        }
        int left=in.nextInt();//左边界
        int right=in.nextInt();//右边界
        func(array,left,right);
        //System.out.println();
    }
    public static void func(int[] array,int left,int right){
        //反转array数组中[left-1,right-1]，部分的数据
        int len=array.length;
        //题目中：数组的第一位是1，但是实际数组的第一位的下标应该是0，所以这里需要减一
        left=left-1;
        right=right-1;
        while(left<right){
            int tmp=array[left];
            array[left]=array[right];
            array[right]=tmp;
            left++;
            right--;
        }
        //按照题目要求打印数组的各个元素
        for(int i=0;i<len;i++){
            if(i!=len-1){
                System.out.print(array[i]+" ");
            }else{
                System.out.print(array[i]);
            }
        }
    }




    public static void main28(String[] args){
        //给定三边判断是否是一个三角形
        // （2边之和大于第3边）
        Scanner sc=new Scanner(System.in);
        while(sc.hasNextDouble()){
            double a=sc.nextDouble();
            double b=sc.nextDouble();
            double c=sc.nextDouble();
            if(a+b>c && a+c>b && b+c>a){
                System.out.println("Yes");
            }else{
                System.out.println("No");
            }
        }
        //System.out.println();
    }




    public static void main27(String[] args){
        //快到碗里来（牛客）
        Scanner sc=new Scanner(System.in);
        while(sc.hasNext()){
            double n=sc.nextDouble();
            double r=sc.nextDouble();
            double ret=2*r*3.14;
            if(ret<n){
                System.out.println("No");
            }else{
                System.out.println("Yes");
            }
        }
        //System.out.println();
    }
    





    public int getValue(int[] gifts, int n) {
        //微信红包
        Map<Integer,Integer> map=new HashMap<>();
        for(int i=0;i<n;i++){
            int ret=gifts[i];
            if(map.containsKey(ret)){
                map.put(ret,map.get(ret)+1);
            }else{
                map.put(ret,1);
            }
        }

        boolean bool=false;
        for(Map.Entry<Integer,Integer> entry : map.entrySet()){
            if(entry.getValue()>n/2){
                return entry.getKey();
            }
        }
        return 0;
    }




    public static void main25(String[] args){
        //小易的升级之路
        //主要的一个点就是一个求：2个数的最大公约数的方法
        Scanner sc=new Scanner(System.in);
        while (sc.hasNextInt()){
            int n=sc.nextInt();
            int a=sc.nextInt();
            int[] array=new int[n];
            for(int i=0;i<n;i++){
                array[i]=sc.nextInt();
                if(array[i]<=a){
                    a+=array[i];
                }else{
                    int ret=func3(a,array[i]);
                    a+=ret;
                }
            }
            System.out.println(a);
        }
        //System.out.println();
    }
    public static int func3(int n,int m){
        //求2个数的最大公约数
        int minn=n>m?m:n;//m和n中的较小值
        int maxx=n>m?n:m;//m和n中的较大值
        for(int i=minn;i>=1;i--){
            if(minn%i==0&&maxx%i==0){
                return i;
            }
        }
        return 0;//有可能其中一个数是0
    }



    public static void main24(String[] args){
        // 找出字符串中
        // 第一个只出现了一次的字符
        Scanner sc=new Scanner(System.in);
        String str=sc.nextLine();
        int len=str.length();
        Map<Character,Integer> map=new HashMap<>();
        for(int i=0;i<len;i++){
            char ch=str.charAt(i);
            if(map.containsKey(ch)==true){
                //map中已经存在这个字符了
                map.put(ch,map.get(ch)+1);
            }else{
                map.put(ch,1);
            }
        }
        boolean bool=true;//没有出现一次的字符，那么bool就是true

        //遍历map寻找第一个value是1的字符
        /*for(Map.Entry<Character,Integer> entry : map.entrySet()){
            if(entry.getValue()==1){
                System.out.println(entry.getKey());
                bool=false;
                break;
            }
        }*/
        //遍历写的没错，就是在调试中看到map内部的字符的顺序发生了改变所以导致
        //找不到哪个是第一个只出现一次的字符了



        for(int i=0;i<len;i++){
            char ch=str.charAt(i);
            if(map.get(ch)==1){
                System.out.println(ch);
                bool=false;
                break;
            }
        }
        if(bool==true){
            System.out.println(-1);
        }
        //System.out.println();
    }





    public static void main22(String[] args){
        //MP3光标位置
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        String str=sc.next();
        int len=str.length();
        if(n<=4){
            //歌曲总数4首以内
            func1(n,str,len);
        }else{
            //歌曲总数多于4首
            func2(n,str,len);
        }
        //System.out.println();
    }
    //所以默认刚开始的时候：光标初始的位置在第一首歌的位置上
    public static void func1(int n,String str,int len){
        //歌曲总数4首以内(<=4)
        int ret=1;//初始的时候
        for(int i=0;i<len;i++){
            if(str.charAt(i)=='U'){
                if(ret==1){
                    //特殊情况1：光标在第一首歌的位置，按了up命令
                    ret=n;
                }else{
                    ret--;
                }
            }else if(str.charAt(i)=='D'){
                if(ret==n){
                    //特殊情况2：光标在最后一首歌的位置，按了down命令
                    ret=1;
                }else{
                    ret++;
                }
            }
        }

        //因为是4首以内，所以就全都打印出来，然后把ret的值打印出来就行了
        for(int i=1;i<=n;i++){
            if(i!=n){
                System.out.print(i+" ");
            }else{
                System.out.print(i);
            }
        }
        System.out.println();
        System.out.println(ret);
    }
    //所以默认刚开始的时候：光标初始的位置在第一首歌的位置上
    //  System.out.println();
    public static void func2(int n,String str,int len){
        //歌曲总数多于4首
        int ret=1;//标记光标的位置在哪里
        int tmp=1;//标记这一页的起始位置是什么
        for(int i=0;i<len;i++){
            char ch=str.charAt(i);
            if(ch=='U'){
                if(ret==1){
                    //特殊翻页
                    ret=n;
                    tmp=n-3;
                    //例如：10 9 8 7    -----》 10-7=3
                    //10和7之间一个是4个数
                }else{
                    ret--;
                    if(ret<tmp){
                        //一般翻页
                        tmp--;
                    }
                }
            }else if(ch=='D'){
                if(ret==n){
                    //特殊翻页
                    tmp=1;
                    ret=1;
                }else{
                    ret++;
                    if(ret>=tmp+4){
                        //一般翻页
                        tmp++;
                    }
                }
            }
        }

        //打印现在所在页的4条数据，以及ret的值
        for(int i=0;i<4;i++){
            if(i!=3){
                System.out.print(tmp+i+" ");
            }else{
                System.out.print(tmp+i);
            }
        }
        System.out.println();
        System.out.println(ret);
    }




    public static void main26(String[] args){
        //洗牌
        Scanner sc=new Scanner(System.in);
        int t=sc.nextInt();//有几组牌需要洗
        while(t!=0){
            int n=sc.nextInt();//有几张牌
            int k=sc.nextInt();//洗牌的次数
            int[] array=new int[2*n];//存放这次要洗的所有牌的数组
            for(int i=0;i<2*n;i++){
                array[i]=sc.nextInt();
            }
            //int[] arr=new int[2*n];
            for(int j=0;j<k;j++){
                array=func(n,array);
            }
            //出来打印数组arrry
            for(int i=0;i<2*n;i++){
                if(i!=2*n-1){
                    System.out.print(array[i]+" ");
                }else{
                    System.out.print(array[i]);
                }
            }
            //System.out.print(arr);
            t--;
            System.out.println();
        }
        //System.out.println();
    }
    public static int[] func(int n,int[] array){
        //返回的arr数组得是：洗牌一次以后，按照从上往下的顺序来返回的才行
        //所以ret得从arr数组的最后一位开始
        int ret=2*n-1;//用来代表arr数组走到哪里了
        int[] arr=new int[2*n];
        int i=n-1;//代表左手的牌[0,n-1]
        int j=2*n-1;//代表右手的牌[n,2*n-1]
        //先放右手的一张在放左手的一张
        //左右手都是从它们的后往前来放的

        while(i>=0&&j>=n){
            arr[ret]=array[j];
            j--;
            ret--;
            arr[ret]=array[i];
            i--;
            ret--;
        }
        return arr;
    }



    public static void main21(String[] args) {
        //查找两个字符串a,b中的最长公共子串
        Scanner sc=new Scanner(System.in);
        String str1=sc.nextLine();
        String str2=sc.nextLine();
        int len1=str1.length();
        int len2=str2.length();
        //默认len2是长的那个，str2是长的那个
        //所以接下来就是比较 交换时刻
        if(len1>len2){
            String strr=str1;
            str1=str2;
            str2=strr;
            int rett=len1;
            len1=len2;
            len2=rett;
        }
        int count=0;
        String str="";
        //所以就是遍历短的那个，去长的里面去找，记录长度ret和匹配的字符串retstr
        for(int i=0;i<len1;i++){
            for(int j=0;j<len2;j++){
                //看这个i和j是否是相等的要是想等的就开始依次往后遍历看看相等的有多少
                //不过继续遍历的时候不能直接用j和i，得用reti和retj，
                //然后还要注意范围，还有一个ret来记录这次匹配的字符个数
                if(str1.charAt(i)==str2.charAt(j)){
                    int ret=0;
                    int reti=i;
                    int retj=j;
                    String retstr="";
                    while(reti<len1&&retj<len2){
                        if(str1.charAt(reti)==str2.charAt(retj)){
                            retstr+=str1.charAt(reti);
                            ret++;
                            reti++;
                            retj++;
                        }else{
                            break;
                        }
                    }
                    if(ret>count){
                        //等到ret>count的时候，就需要修改最长的字串个数和子字符串
                        str=retstr;
                        count=ret;
                    }
                }
            }
        }
        System.out.println(str);


        /*Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int a = in.nextInt();
            int b = in.nextInt();
            System.out.println(a + b);
        }*/
    }




    public static void main20(String[] args){
        //2个字符串之间的公共字串的最大长度的计算
        Scanner sc=new Scanner(System.in);
        String str1=sc.next();
        String str2=sc.next();
        int len1=str1.length();
        int len2=str2.length();
        int count=0;
        for(int i=0;i<len1;i++){
            for(int j=0;j<len2;j++){
                //看这个i和j是否是相等的要是想等的就开始依次往后遍历看看相等的有多少
                //不过继续遍历的时候不能直接用j和i，得用reti和retj，
                //然后还要注意范围，还有一个ret来记录这次匹配的字符个数
                if(str1.charAt(i)==str2.charAt(j)){
                    int ret=0;
                    int reti=i;
                    int retj=j;
                    while(reti<len1&&retj<len2){
                        if(str1.charAt(reti)==str2.charAt(retj)){
                            ret++;
                            reti++;
                            retj++;
                        }else{
                            break;
                        }
                    }
                    if(ret>count){
                        count=ret;
                    }
                }
            }
        }
        System.out.println(count);
    }



    public static void main19(String[] args){
        //字符串反转
        //逆着输出一个字符串
        // 就可以解决这个题了
        Scanner sc=new Scanner(System.in);
        String str=sc.next();
        int len=str.length();
        for(int i=len-1;i>=0;i--){
            System.out.print(str.charAt(i));
        }
        //System.out.println();
    }




    public static void main18(String[] args){
        //汽水瓶（可以喝到的汽水瓶数）
        Scanner sc=new Scanner(System.in);
        while (sc.hasNextInt()) {
            int n=sc.nextInt();
            if(n==0){
                break;
            }
            int count=func8(n);
            System.out.println(count);
        }
    }
    public static int func8(int n){
        int count=0;//记录她最多可以喝到的汽水的瓶数
        while(n>1){
            count+=n/3;
            //n就是空瓶 的个数
            //三个空瓶可以换一瓶汽水
            int ret=n/3;
            //汽水喝完以后，就会变成空瓶
            n=n%3+ret;
            if(n==2){
                //因为可以和老板届空瓶，但是要还
                //所以，当我们有2个空瓶的时候，可以借一个，然后换成汽水，然后喝完以后还回去就行了
                //如果我们还有一个空瓶的话，就不行了，就不能在换了
                n=3;
            }
        }
        return count;
    }



    public static void main16(String[] args){
        //杨辉三角的变形（是有规律性的，可以一行行的求出来找规律）
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt();
        if(n==1||n==2){
            // 如果n是1或者2，就是返回-1
            //  1  2  ---》 -1
            System.out.println(-1);
        }else if(n%2!=0){
            // 3  5  7  9  11   ---》2       如果n是一个奇数，就返回2
            System.out.println(2);
        }else if(n%2==0&&n%4==0){
            // 4  8   ---》3        如果是一个偶数，如果是4的倍数，就返回3
            System.out.println(3);
        }else if(n%2==0&&n%4!=0){
            // 6  10  ----》4      如果是一个偶数，如果不是4的倍数，就返回4
            System.out.println(4);
        }
        //System.out.println();
    }




    public static void main17(String[] args){
        //字符串通配符
        Scanner sc=new Scanner(System.in);
        //  * 可以匹配0个及以上的字符个数
        // ?  只能匹配一个字符
        //  匹配是不区分大小写的
        String str1=sc.next();
        String str4=str1.toLowerCase();//所以这里我就统统转成小写的了  要记得str4是第一个字符串
        String str2=sc.next();
        String str3=str2.toLowerCase();//所以这里我就统统转成小写的了  str3是第二个字符串
        int len1=str1.length();
        int len2=str2.length();
        char[] array=str3.toCharArray();// array这个字符串数组是str3转换来的，所以array也是代表了第二个字符串
        boolean bool=true;   //使用bool，来接受func方法的返回值
        bool=func(str4,array,len1,len2);
        System.out.println(bool); //打印bool的结果
    }
    public static boolean func(String str4,char[] array,int len1,int len2){
        //主要思路：
        //从前往后遍历array数组，同时用j来控制遍历str4
        //首先判断array数组遍历到的这个字符串是否是:（能被*和?匹配的字符仅由英文字母和数字0到9组成）
        // 是的话，就当作一个正常的字符，要不就是不正常的（在这个题里面）
        boolean bool=true;
        if(str4.charAt(len1-1)!='*'&&str4.charAt(len1-1)!='?'&&str4.charAt(len1-1)!=array[len2-1]){
            //浅浅判断一下，万一str4的最后一位，既不是*也不是？，
            //然后str4的最后一位又和array数组的最后一位字符也不相等，所以str4和array就肯定是不匹配的，就返回false
            bool=false;
            return bool;
        }
        if(len1==1&&len2!=1){
            //在这里，浅浅判断一下，一种特殊的情况
            //如果str4的长度为1 ，但是array的长度大于1，然后str4的这个唯一的字符，不是*,那么就肯定无法匹配了
            if(str4.charAt(0)!='*'){
                bool=false;
                return bool;
            }
        }

        int j=0;
        //开始遍历
        for(int i=0;i<len2;i++){
            char ch=array[i];//每一次遍历array数组时下标为i的字符
            char ret=str4.charAt(j);//str4这个字符串的j下标对应的字符
            if(ch>='0'&&ch<='9'||ch>='a'&&ch<='z'){
                //当ch是一个正常的字符
                if(ret=='*'){
                    //当ret是*的时候
                    // * 可以匹配0个及以上的字符个数
                    if(j<len1-1){
                        //str4这个字符串不能越界，但是可以停下来等待array数组
                        j++;
                    }
                    //str4这个字符串加加，以后对应的字符如果是一个正常的字符，那就去和array数组的字符去比较
                    if(str4.charAt(j)!='*'&&str4.charAt(j)!='?'){
                        //去找：array数组中和str4这个字符串此时对应的字符相等的下标
                        while(str4.charAt(j)!=array[i]){
                            i++;
                        }
                        //对于array数组中和此时str4对于的字符相等的字符都要过去，所以while
                        while(str4.charAt(j)==array[i]){
                            i++;
                            if(i==len2){
                                //防止越界
                                return bool;
                            }
                        }
                        /*if(str4.charAt(j)!=array[i]){
                            if(j<len1-1){
                                j++;
                            }
                        }*/
                        if(j<len1-1){
                            //防止越界
                            j++;
                        }
                        i--;
                        //这里i--，是因为，这个总体是一个for循环，等这个i到了上面以后，它还会被++一下，
                        //所以这里应该--一下，才能保证遍历没有落下array中的字符
                    }
                }else if(ret=='?'){
                    //   ?  只能匹配一个字符
                    // 所以让str4的下标j++
                    if(j<len1-1){
                        j++;
                    }
                }else{
                    //ret也是一个正常的字符
                    if(ret!=ch){
                        //2者都是正常的字符，如果不相等就返回false，就是不匹配的
                        bool=false;
                        return bool;
                    }
                    if(j<len1-1){
                        //2者相等的话，就简单的加加，继续去比下一个字符
                        j++;
                    }
                }
            }else {
                //当ch不是一个正常的字符
                if (ret == '*' || ret == '?') {
                    //如果此时ret是*或者？,那就是不匹配的，就返回false
                    bool = false;
                    return bool;
                }
            }
        }
        //上面的判断都没有返回的话，就是匹配了，就返回true
        return bool;
    }



    public static void main15(String[] args){
        //统计每个月兔子的总数
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int count=func5(n);
        System.out.println(count);
    }
    //public static int count=1;
    public static int func5(int n){
        //递归思想
        //递归的结束条件：就是n是1或者2
        if(n==1||n==2){
            return 1;
        }
        //一只兔子从她出生，她成长了2个月以后，她出生的第三个月才可以开始，从这个月开始，每个月生一只小兔子
        //初始状态是：只有一只兔子，并且她刚出生
        //所以想法就是，第一个月和第二个月的时候，（n==1或者n==2)的时候，只有一只兔子
        //然后第n个月的兔子的数量就是：第n-1月的兔子的个数  +  第n-2月的兔子的数量生的宝宝的数量
        //一只兔子她一个月只能生一只小兔子
        return func5(n-1)+func5(n-2);
    }



    public static void main14(String[] args){
        //计算某字符出现的次数（这个字符的大小写都算）
        Scanner sc = new Scanner(System.in);
        String str=sc.nextLine();
        String str2=str.toLowerCase();
        String str1=sc.next();
        String str3=str1.toLowerCase();
        char ret=str3.charAt(0);
        int len=str.length();
        int count=0;
        for(int i=0;i<len;i++){
            char ch=str2.charAt(i);
            if(ch==ret){
                count++;
            }
        }
        System.out.println(count);
    }




    public static void main13(String[] args){
        //完全数的计算(一个数的所有的真因子之和恰好等于它自己本身)
        //真因子：就是除了自身以外的约数
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int count=0;
        //真因子，除了自身以外的约数，所以1肯定不是一个完全数
        for(int i=2;i<=n;i++){
            if(func3(i)==true){
                count++;
            }
        }
        System.out.println(count);
    }
    public static boolean func3(int n){
        int count=0;
        for(int i=1;i<=n/2;i++){
            if(n%i==0){
                count+=i;
            }
        }
        if(count==n){
            return true;
        }
        return false;
    }




    public static void main12(String[] args){
        //计算一个正整数的二进制中1的个数
        Scanner sc=new Scanner(System.in);
        while (sc.hasNextInt()) {// 注意，如果输入是多个测试用例，请通过while循环处理多个测试用例
            int n = sc.nextInt();
            System.out.println(func4(n));
        }
        //System.out.println();
    }
    public static int func4(int n){
        int count=0;
        while(n!=0){
            int ret=n%2;
            n=n/2;
            if(ret==1){
                count++;
            }
        }
        return count;
    }




    public int[] twoSum(int[] nums, int target) {
        //求两数之和等于一个特定值的2个数
        int len=nums.length;
        Map<Integer,Integer> map=new HashMap<>();
        for(int i=0;i<len;i++){
            map.put(nums[i],i);
        }

        int[] arr=new int[2];
        for(int i=0;i<len;i++){
            int ret=target-nums[i];
            if(map.containsKey(ret)){
                int tmp=map.get(ret);
                if(i!=tmp){
                    arr[0]=i;
                    arr[1]=tmp;
                    break;
                }
            }
        }

        return arr;
    }



    public static void main11(String[] args){
        //参数解析，双引号内部是一个参数（就算它的内部有空格也是一个参数）；
        // 不在双引号内部的：参数分隔符是空格
        Scanner sc=new Scanner(System.in);
        String str=sc.nextLine();
        int len=str.length();
        int count=0;
        //String[] array=new String[len];
        boolean bool=true;//true代表还没有遇到引号
        //如果是false那么就是遇到引号了，只有在遇到一次引号才可以置为true
        //第一个for是为了求出分解后的参数的个数
        for(int i=0;i<len;i++){
            //字符串的长度范围是[1,1000]
            if(str.charAt(i)=='"'&&bool==true){
                //count++;
                //第一次遇到引号
                //System.out.print(str.charAt(i));
                bool=false;
            }else if(str.charAt(i)=='"'&&bool==false){
                //第二次遇到引号
                //System.out.print(str.charAt(i));
                bool=true;
                //System.out.println();
            }else if(str.charAt(i)!=' '){
                //System.out.print(str.charAt(i));
            }else if(i+1<len&&str.charAt(i+1)!=' '&&str.charAt(i)==' '&&bool==true){
                count++;
                //System.out.println();
            }
        }
        System.out.println(count+1);

        bool=true;

        //第二个for循环是为了打印每一个分解以后的参数
        for(int i=0;i<len;i++){
            //字符串的长度范围是[1,1000]
            if(str.charAt(i)=='"'&&bool==true){
                //第一次遇到引号
                bool=false;
            }else if(str.charAt(i)=='"'&&bool==false){
                //第二次遇到引号
                bool=true;
            }else if(str.charAt(i)!=' '){
                System.out.print(str.charAt(i));
            }else if(i+1<len&&str.charAt(i+1)!=' '&&str.charAt(i)==' '&&bool==true){
                System.out.println();
            }else if(bool==false){
                System.out.print(str.charAt(i));
                //在双引号内部的任何字符都应该被打印，包括空格，所以当bool是false的时候，
                //遇到的任意字符都会被打印出来
            }
        }
        //System.out.println();
    }





    public static int binInsert(int n, int m, int j, int i) {
        //二进制的插入
        // write code here
        // 按照例子来看，对于这个n和m这2个数都是： 应该是从右边往左边数，然后下标是从0开始的
        //要找到的i和j 的下标的位置是按照下标从右到左依次递增的方式来找的，
        //但是修改字符串和遍历字符串的时候都是按照下标从左到右递增的方法来走的
        //这个区别要弄好

        //但是在实际情况下，一个字符串的下标是从左到右依次递增，所以在下边的修改字符串的时候需要好好看到这一点，并且注意一下，
        //就是要把这个逆着的下标转换成对于的正着的下标去
        // 1  0 0 0 0 0 0 0 0 0 0
        // 10 9 8 7 6 5 4 3 2 1 0
        // 10011
        //  2  和  6
        // 10001001100
        //     6543210
        StringBuilder strn=new StringBuilder(Integer.toBinaryString(n));
        String strm=Integer.toBinaryString(m);
        int lenm=strm.length();
        int lenn=strn.length();
        int ret=lenm-1;

        // 按照例子来看，对于这个n和m这2个数都是： 应该是从右边往左边数，然后下标是从0开始的
        //但是在实际情况下，一个字符串的下标是从左到右依次递增，所以在下边的修改字符串的时候需要好好看到这一点，并且注意一下，
        //就是要把这个逆着的下标转换成对于的正着的下标去
        for(int ps=lenn-1-j;ps>=lenn-1-i;ps--){
            if(ret<0){
                break;
            }
            char chm=strm.charAt(ret);
            ret--;
            strn.setCharAt(ps,chm);
        }

        int count=0;//最后得到的新数
        int h=lenn-1;//每一位2的几次幂
        int p=0;//n对应的字符串的下标（下标是从左到右依次递增）
        while(p<lenn){
            int tmp=strn.charAt(p)-'0';
            count+=tmp*Math.pow(2,h);
            h--;
            p++;
        }

        return count;
    }

    public static void main10(String[] args) {
        int m=19;
        //10011
        int n=1024;
        //1000000000
        int i=6;
        int j=2;
        int ret=binInsert(n,m,j,i);
        System.out.println(ret);
        //1001001100
    }





    public static void main9(String[] args){
        //查找组成一个偶数（大于2）的 最接近的 2个素数
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int[] array=new int[2];
        array=func2(n);
        //Arrays.sort(array);
        System.out.println(array[0]);
        System.out.println(array[1]);
    }
    public static int[] func2(int n){
        //素数是除了1和它本身，不能被其他的数整除的数
        //1和0都不是素数
        int[] array=new int[2];
        int left=2;//2也是素数
        int right=n-2;
        if(left<=right&&func1(right)){
            //如果left<right并且right和left都是素数就放到数组里面去
            array[0]=left;
            array[1]=right;
        }

        int count=0;//代表left和right之间的距离的最小值
        if(left<=right){
            count=right-left;
        }else{
            return array;
        }


        while(left<=right){
            left++;
            while(left<n&&!func1(left)){
                left++;
            }
            if(left==n){
                return array;
            }
            right=n-left;//left+right==n
            if(func1(right)){
                int ret=right-left;
                if(ret>=0&&ret<count){
                    count=ret;
                    array[0]=left;
                    array[1]=right;
                }
            }
        }
        return array;
    }
    public static boolean func1(int n){
        //判断一个整数是不是素数
        for(int i=n/2;i>1;i--){
            if(n%i==0){
                return false;
            }
        }
        return true;
    }




    public static void func(byte n){
        n=n++;
    }
    public static void main8(String[] args) {
        byte a=127;
        byte b=127;
        //byte类型的数据的范围是：-128 —— 127
        func(++a);
        func(b);
        System.out.println(a);//-128
        System.out.println(b);//127
    }



    public class UnusualAdd {
        //不允许使用算术运算符，然后去求A+B的值并返回
        public int addAB(int A, int B) {
            // write code here
            //使用移位运算符,操作二进制
            //在二进制中，按位异或得到不进位的数字，按位与得到需要进位的数字。
            if((A&B)==0){
                return A^B;
            }else{
                //递归
                return addAB((A&B)<<1,A^B);
                //<<左移操作符相当于是*2
            }
        }
    }



    public static void main3(String[] args){
        //走格子的方案数
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int m=sc.nextInt();
        int ret=func(m,n);
        System.out.println(ret);
    }
    public static int func(int m,int n){
        if(n==1||m==1){
            //当有一个数是1的时候，此时路径数是：m+n
            return m+n;
        }
        //递归求解，只能往右走和往下走
        int right=func(m,n-1);
        int down=func(m-1,n);
        return right+down;
    }



    public static void main2(String[] args) {
        int i=0;
        Integer j=new Integer(0);
        System.out.println(i==j);
        System.out.println(j.equals(i));
    }



    public static void main7(String[] args){
        //统计回文
        Scanner sc=new Scanner(System.in);
        String str1=sc.next();
        String str2=sc.next();
        //把str2插入到str1中，先简单一点来想，就是把2这个字符串
        //是每次整体插入到1这个字符串的位置中的
        int len1=str1.length();
        int len2=str2.length();
        int count=0;
        for(int i=0;i<=len1;i++){
            StringBuilder str=new StringBuilder(str1);
            //每次都是插到1的这个位置的后面去
            str.insert(i,str2);
            //这个insert方法，的意思是每次插入的位置是：
            //是从i下标这里开始插入，就是说如果i等于0，那就说明是把2插入到了1的头部
            //如果i等于len1，那么就说明是把2插入到了1的尾部
            boolean bool=func2(str);
            if(bool==true){
                count++;
            }
        }
        System.out.println(count);
    }
    public static boolean func2(StringBuilder str){
        //判断一个字符串是否是回文结构
        int len=str.length();
        int left=0;
        int right=len-1;
        while(left<right){
            if(str.charAt(left)!=str.charAt(right)){
                return false;
            }
            left++;
            right--;
        }
        return true;
    }


    public static void main4(String[] args){
        //判断一个字符串数组是否是按照字符串长度排序，或者按照字典序排序的
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        String[] array=new String[n];
        for(int i=0;i<n;i++){
            array[i]=sc.next();
        }
        boolean bool1=func1(array,n);//是否是按照字典序排序
        boolean bool2=func2(array,n);//是否是按照长度排序
        if(bool1&&!bool2){
            System.out.println("lexicographically");
        }else if(!bool1&&bool2){
            System.out.println("lengths");
        }else if(bool1&&bool2){
            System.out.println("both");
        }else if(!bool1&&!bool2){
            System.out.println("none");
        }
        //System.out.println();
    }
    public static boolean func1(String[] array,int n){
        //是否是按照字典序排序
        if(n==0){
            return true;
        }
        String str1=array[0];
        for(int i=1;i<n;i++){
            String str2=array[i];
            if(str1.compareTo(str2)>0){
                //使用字符串的比较方法
                return false;
            }
            str1=str2;
        }
        return true;
    }
    public static boolean func2(String[] array,int n){
        //是否是按照长度排序
        if(n==0){
            return true;
        }
        int len1=array[0].length();
        for(int i=1;i<n;i++){
            int len2=array[i].length();
            if(len1>len2){
                return false;
            }
            len1=len2;
        }
        return true;
    }


    public static void main5(String[] args){
        //最小公倍数
        Scanner sc=new Scanner(System.in);
        int a=sc.nextInt();
        int b=sc.nextInt();
        int ret=func1(a,b);
        System.out.println(ret);
    }
    public static int func1(int a,int b){
        int ret=(a>b?a:b);//选出2个数中的较大值
        while(ret%a+ret%b!=0){
            //开始去找a和b的最小公倍数，找到就返回了
            ret++;
        }
        return ret;
    }


    public static void main6(String[] args){
        //求一个整数N最少经过几步可以变成一个斐波那契数，每步是+1或者-1
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        //加一或者减一，可以都试试，看看什么时候它是一个斐波那契数就好了
        int[] arr=func(n);
        int minn=arr[0];
        int maxn=arr[1];
        int mincount=0;
        int ret=n;
        while(ret!=minn){
            mincount++;
            ret--;
        }
        ret=n;
        int maxcount=0;
        while(ret!=maxn){
            maxcount++;
            ret++;
        }
        System.out.println((mincount<maxcount?mincount:maxcount));
    }
    public static int[] func(int n){
        //func方法来找到n附近的2个斐波那契数，一个比n大，一个比n小
        int[] arr=new int[2];
        int a0=0;
        int a1=1;
        int a2=a0+a1;
        while(a2<n){
            a0=a1;
            a1=a2;
            a2=a0+a1;
        }
        // a2>=n的时候了
        arr[0]=a1;//一个比它<
        arr[1]=a2;//一个比它>=
        return arr;
    }



    public static void main1(String[] args){
        //统计回文
        Scanner sc=new Scanner(System.in);
        String str1=sc.next();
        String str2=sc.next();
        //把str2插入到str1中，先简单一点来想，就是把2这个字符串
        //是每次整体插入到1这个字符串的位置中的
        int len1=str1.length();
        int len2=str2.length();
        int count=0;
        for(int i=0;i<=len1;i++){
            StringBuilder str=new StringBuilder(str1);
            //每次都是插到1的这个位置的后面去
            str.insert(i,str2);
            //这个insert方法，的意思是每次插入的位置是：
            //是从i下标这里开始插入，就是说如果i等于0，那就说明是把2插入到了1的头部
            //如果i等于len1，那么就说明是把2插入到了1的尾部
            boolean bool=func(str);
            if(bool==true){
                count++;
            }
        }
        System.out.println(count);
    }
    public static boolean func(StringBuilder str){
        //判断一个字符串是否是回文结构
        int len=str.length();
        int left=0;
        int right=len-1;
        while(left<right){
            if(str.charAt(left)!=str.charAt(right)){
                return false;
            }
            left++;
            right--;
        }
        return true;
    }



    public int StrToInt(String str) {
        //把一个字符串变成一个整数
        int len=str.length();
        if(len==0){
            return 0;
        }
        char ch=str.charAt(0);
        int ret=1;
        if(ch=='-'){
            //是一个负数
            ret=-1;
        }

        int count=0;
        int t=0;
        for(int i=len-1;i>=0;i--){
            char tmp=str.charAt(i);
            if(tmp=='-'||tmp=='+'&&i==0){
                //return 0;
            }else if(tmp>='0'&&tmp<='9'){
                int n=(int)(tmp-'0');
                count+=n*Math.pow(10,t);
                t++;
            }else{
                return 0;
            }

        }
        return count*ret;
    }
}



    class Solution {
    //把一个字符串变成一个整数
    public int StrToInt(String str) {
        if(str==null){
            return 0;
        }
        int len=str.length();
        int count=0;
        boolean bool=false;//判断是否是负数

        for(int i=0;i<len;i++){
            char ch=str.charAt(i);
            if(ch>='0'&&ch<='9'){
                count+=Math.pow(10,len-i-1)*(ch-'0');
                //不让使用库里面的库函数，所以数字都得自己加上去
            }else if(i!=0){
                return 0;
            }
            else if(i==0){
                if(ch=='-'||ch=='+'){
                    if(ch=='-'){
                        bool=true;
                    }
                }else {
                    return 0;
                }
            }

        }
        if(bool==false){
            return count;
        }else{
            return -1*count;
        }
    }
}



    class Parenthesis {
    //合法括号序列的判断
    public boolean chkParenthesis(String A, int n) {
        // write code here
        //合法的括号肯定是偶数个字符
        if (n % 2 != 0) {
            return false;
        }
        //建一个栈，左括号入栈，遇到右括号就出栈,遇到不是右括号又不是左括号的时候就返回false
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < n; i++) {
            char ch = A.charAt(i);
            if (ch == '(') {
                stack.add(ch);
            } else if (ch == ')') {
                if (stack.empty()) {
                    return false;
                } else {
                    stack.pop();
                }
            } else {
                return false;
            }
        }
        return true;
    }
}

